package sword.chapter9Heap;

import java.util.*;

/**
 * 和最小的k个数对
 *
 * 最大堆，PriorityQueue<int[]> maxHeap，值存储数组
 *
 * @author K
 * @date 2021-12-14 20:22
 */
public class S61KSmallestPairs {
    public static List<List<Integer>> s61(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return (o2[0] + o2[1]) - (o1[0] + o1[1]);
            }
        });

        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (maxHeap.size() < k) {
                    maxHeap.offer(new int[]{nums1[i], nums2[j]});
                } else if (nums1[i] + nums2[j] < maxHeap.peek()[0] + maxHeap.peek()[1]) {
                    maxHeap.poll();
                    maxHeap.offer(new int[]{nums1[i], nums2[j]});
                }
            }
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            int[] element = maxHeap.poll();
            result.add(Arrays.asList(element[0], element[1]));
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 5, 13, 21};
        int[] nums2 = {2, 4, 9, 15};
        List<List<Integer>> result = s61(nums1, nums2, 3);
        System.out.println();
    }
}
